Search Results

Documents authored by Tavenas, Sébastien

Document
DOI: 10.4230/LIPIcs.CCC.2023.28
Towards Optimal Depth-Reductions for Algebraic Formulas

Authors: Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula. Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth O(log d) and size poly(s). Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas. This improves on previous results in the regime when d is small (i.e., d = s^o(1)). In particular, for the setting of d = O(log s), along with a result of Raz (STOC 2010, JACM 2013), our result implies the same depth reduction even for inhomogeneous formulas. This is particularly interesting in light of recent algebraic formula lower bounds, which work precisely in this "low-degree" and "low-depth" setting. We also show that these results cannot be improved in the monotone setting, even for commutative formulas.
Cite as

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas. Towards Optimal Depth-Reductions for Algebraic Formulas. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.CCC.2023.28,
  author =	{Fournier, Herv\'{e} and Limaye, Nutan and Malod, Guillaume and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{Towards Optimal Depth-Reductions for Algebraic Formulas}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.28},
  URN =		{urn:nbn:de:0030-drops-182986},
  doi =		{10.4230/LIPIcs.CCC.2023.28},
  annote =	{Keywords: Algebraic formulas, depth-reduction}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.32
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

Authors: Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits. More specifically, our previous work applied the well-known partial derivative method in a new setting, that of lopsided set-multilinear polynomials. A set-multilinear polynomial P ∈ 𝔽[X_1,…,X_d] (for disjoint sets of variables X_1,…,X_d) is a linear combination of monomials, each of which contains one variable from X_1,…,X_d. A lopsided space of set-multilinear polynomials is one where the sets X_1,…,X_d are allowed to have different sizes (we use the adjective "lopsided" to stress this feature). By choosing a suitable lopsided space of polynomials, and using a suitable version of the partial-derivative method for proving lower bounds, we were able to prove constant-depth superpolynomial set-multilinear formula lower bounds even for very low-degree polynomials (as long as d is a growing function of the number of variables N). This in turn implied lower bounds against general formulas of constant-depth. A priori, there is nothing stopping these techniques from giving us lower bounds against algebraic formulas of any depth. We investigate the extent to which this lower bound can extend to greater depths. We prove the following results. 1) We observe that our choice of the lopsided space and the kind of partial-derivative method used can be modeled as the choice of a multiset W ⊆ [-1,1] of size d. Our first result completely characterizes, for any product-depth Δ, the best lower bound we can prove for set-multilinear formulas of product-depth Δ in terms of some combinatorial properties of W, that we call the depth-Δ tree bias of W. 2) We show that the maximum depth-3 tree bias, over multisets W of size d, is Θ(d^{1/4}). This shows a stronger formula lower bound of N^{Ω(d^{1/4})} for set-multilinear formulas of product-depth 3, and also puts a non-trivial constraint on the best lower bounds we can hope to prove at this depth in this framework (a priori, we could have hoped to prove a lower bound of N^{Ω(Δ d^{1/Δ})} at product-depth Δ). 3) Finally, we show that for small Δ, our proof technique cannot hope to prove lower bounds of the form N^{Ω(d^{1/poly(Δ)})}. This seems to strongly hint that new ideas will be required to prove lower bounds for formulas of unbounded depth.
Cite as

Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 32:1-32:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{limaye_et_al:LIPIcs.CCC.2022.32,
  author =	{Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{32:1--32:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.32},
  URN =		{urn:nbn:de:0030-drops-165942},
  doi =		{10.4230/LIPIcs.CCC.2022.32},
  annote =	{Keywords: Partial Derivative Method, Barriers to Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.15
Nonnegative Rank Measures and Monotone Algebraic Branching Programs

Authors: Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
Inspired by Nisan’s characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.
Cite as

Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas. Nonnegative Rank Measures and Monotone Algebraic Branching Programs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.FSTTCS.2019.15,
  author =	{Fournier, Herv\'{e} and Malod, Guillaume and Szusterman, Maud and Tavenas, S\'{e}bastien},
  title =	{{Nonnegative Rank Measures and Monotone Algebraic Branching Programs}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.15},
  URN =		{urn:nbn:de:0030-drops-115774},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.15},
  annote =	{Keywords: Elementary symmetric polynomials, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.21
Reconstruction of Full Rank Algebraic Branching Programs

Authors: Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
An algebraic branching program (ABP) A can be modelled as a product expression X_1 X_2 ... X_d, where X_1 and X_d are 1 x w and w x 1 matrices respectively, and every other X_k is a w x w matrix; the entries of these matrices are linear forms in m variables over a field F (which we assume to be either Q or a field of characteristic poly(m)). The polynomial computed by A is the entry of the 1 x 1 matrix obtained from the product X_1 X_2 ... X_d. We say A is a full rank ABP if the w^2(d-2) + 2w linear forms occurring in the matrices X_1, X_2, ... , X_d are F-linearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an m-variate polynomial f of degree at most m, the algorithm outputs a full rank ABP computing f if such an ABP exists, or outputs 'no full rank ABP exists' (with high probability). The running time of the algorithm is polynomial in m and b, where b is the bit length of the coefficients of f. The algorithm works even if X_k is a w_{k-1} x w_k matrix (with w_0 = w_d = 1), and v = (w_1, ..., w_{d-1}) is unknown. The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMM_{v,d}, the (1,1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to v in N^{d-1}. At its core, the algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM_{v,d} and the 'layer spaces' of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMM_{v,d} and show that IMM_{v,d} is characterized by its group of symmetries.
Cite as

Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 21:1-21:61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.CCC.2017.21,
  author =	{Kayal, Neeraj and Nair, Vineet and Saha, Chandan and Tavenas, S\'{e}bastien},
  title =	{{Reconstruction of Full Rank Algebraic Branching Programs}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{21:1--21:61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.21},
  URN =		{urn:nbn:de:0030-drops-75318},
  doi =		{10.4230/LIPIcs.CCC.2017.21},
  annote =	{Keywords: Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.15
On the Sensitivity Conjecture for Disjunctive Normal Forms

Authors: Karthik C. S. and Sébastien Tavenas

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
The sensitivity conjecture of Nisan and Szegedy [CC'94] asks whether for any Boolean function f, the maximum sensitivity s(f), is polynomially related to its block sensitivity bs(f), and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open. In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function f admitting the Normalized Block property, bs(f) <= 4 * s(f)^2. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property. Recently, Gopalan et al. [ITCS'16] showed that every Boolean function f is uniquely specified by its values on a Hamming ball of radius at most 2 * s(f). We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.
Cite as

Karthik C. S. and Sébastien Tavenas. On the Sensitivity Conjecture for Disjunctive Normal Forms. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{s._et_al:LIPIcs.FSTTCS.2016.15,
  author =	{S., Karthik C. and Tavenas, S\'{e}bastien},
  title =	{{On the Sensitivity Conjecture for Disjunctive Normal Forms}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.15},
  URN =		{urn:nbn:de:0030-drops-68504},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.15},
  annote =	{Keywords: Boolean function, Sensitivity, Block sensitivity, DNF}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.33
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Authors: Neeraj Kayal, Chandan Saha, and Sébastien Tavenas

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We show an almost cubic lower bound on the size of any depth three arithmetic circuit computing an explicit multilinear polynomial in n variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson [CCC, 1999].
Cite as

Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.ICALP.2016.33,
  author =	{Kayal, Neeraj and Saha, Chandan and Tavenas, S\'{e}bastien},
  title =	{{An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.33},
  URN =		{urn:nbn:de:0030-drops-63126},
  doi =		{10.4230/LIPIcs.ICALP.2016.33},
  annote =	{Keywords: arithmetic circuits, depth-3 circuits, shifted partials}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.16
On the Sensitivity Conjecture for Read-k Formulas

Authors: Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision tree depth, and degree over R, are all polynomially related to one another. The sensitivity conjecture states that there is also a polynomial relationship between sensitivity and block sensitivity, thus supplying the "missing link". Since its introduction in 1991, the sensitivity conjecture has remained a challenging open question in the study of Boolean functions. One natural approach is to prove it for special classes of functions. For instance, the conjecture is known to be true for monotone functions, symmetric functions, and functions describing graph properties. In this paper, we consider the conjecture for Boolean functions computable by read-k formulas. A read-k formula is a tree in which each variable appears at most k times among the leaves and has Boolean gates at its internal nodes. We show that the sensitivity conjecture holds for read-once formulas with gates computing symmetric functions. We next consider regular formulas with OR and AND gates. A formula is regular if it is a leveled tree with all gates at a given level having the same fan-in and computing the same function. We prove the sensitivity conjecture for constant depth regular read-k formulas for constant k.
Cite as

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.MFCS.2016.16,
  author =	{Bafna, Mitali and Lokam, Satyanarayana V. and Tavenas, S\'{e}bastien and Velingker, Ameya},
  title =	{{On the Sensitivity Conjecture for Read-k Formulas}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.16},
  URN =		{urn:nbn:de:0030-drops-64317},
  doi =		{10.4230/LIPIcs.MFCS.2016.16},
  annote =	{Keywords: sensitivity conjecture, read-k formulas, analysis of Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.642
Building Efficient and Compact Data Structures for Simplicial Complexes

Authors: Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called Maximal Simplex Tree (MxST) and Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.
Cite as

Jean-Daniel Boissonnat, Karthik C. S., and Sébastien Tavenas. Building Efficient and Compact Data Structures for Simplicial Complexes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 642-657, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SOCG.2015.642,
  author =	{Boissonnat, Jean-Daniel and S., Karthik C. and Tavenas, S\'{e}bastien},
  title =	{{Building Efficient and Compact Data Structures for Simplicial Complexes}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{642--657},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.642},
  URN =		{urn:nbn:de:0030-drops-50981},
  doi =		{10.4230/LIPIcs.SOCG.2015.642},
  annote =	{Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact